The event-ordering certification technology contains a technology for certifying the occurrence order of a plurality of events accompanied with generation of digital data and a technology for certifying contents of the digital data generated by the events.
With activisation of Web-based commerce on the Internet and magnified availability in managing digital documents in recent years, there is required a mechanism of electronic authentication for a third party to certify who and when the digital data was generated and/or communicated and what the digital data was formed by. The electronic authentication includes various functions of: specifying transmitter/receiver of the digital data; confirming arrival of the data; certifying context of digital documents, such as transmission/reception; detecting a tamper; storing electronic documents and so on. The event-ordering certification technology accomplishes the functions of certifying the context of digital documents and detecting the tamper.
FIG. 1 is a diagram explaining an event-ordering certification system employing this event-ordering certification technique. In an event-ordering certification system 900 shown in FIG. 1, when a user (demander, verifier, etc.) 30 transmits data objective of event-ordering certification to an event-ordering certification apparatus 10, it generates an event-ordering receipt certificate having data representing a receiving order of the objective data required by the user 30 and sends the event-ordering receipt certificate to the user 30. When adopting a digital signature as major anti-counterfeit/certification means in accordance with PKI (Public Key Infrastructure), the event-ordering receipt certificate is generally constructed to involve a digital signature for objective data for signature where the receiving order is attached to the objective data sent from the user 30. Note that in the following descriptions, the terminology “event-ordering receipt certificate” will be referred to as “event-ordering receipt”, after.
As for this event-ordering certification system adopting the digital signature as a main base for authenticity of this event-ordering receipt, there are pointed out various problems in view of falseness in the event-ordering certification apparatus 10, term of validity of the event-ordering receipt, aspects of system operation and so on. Therefore, there is also proposed an event-ordering certification method that does not adopt the digital signature as the main base for authenticity of this event-ordering receipt. For instance, a method with Linear Linking Protocol is disclosed in nonpatent literatures No. 1 (S. Haber and W. Stornetta, How to Time-Stamp a Digital Document, Journal of Crytology, Vol. 3, No. 2, pp 99-111, 1991) and No. 2 (J.-J. Quisquater, H. Massias, J. S. Avila, B. Van Rompay: Specification and implementation of a timstamping System, Technical Report of Universite Cathoilique de Louvain, 1999, URL: www dice.ucl.ac.be/crpto/TIMESEC/TR4.tgzl). With this method with Linear Linking Protocol, it is possible to provide the system as a whole with high safety even if the event-ordering certification apparatus 10 is not reliable. FIG. 2 is a diagram to explain an event-ordering certification system by Linear Linking Protocol that does not rely upon PKI. In FIG. 2, the event-ordering certification system 910 is constructed so as to produce a link information Ln correlating a plurality of users' data (hash values) objective of event-ordering certification with each other and send event-ordering receipts including the link information Ln to the users 30. Each of the event-ordering receipts is adapted so as to depend on all of the event-ordering receipts that have been produced previously. Then, as parts (LM, LN) of the link information are published on mass-media (e.g. newspapers) periodically, it is possible to prevent falseness of the event-ordering certification apparatus 10, whereby the reliability of the whole system can be improved.
However, the above-mentioned method of Linear Linking Protocol requires mutual collaboration among the users 30 in order to detect the falseness of the event-ordering certification apparatus 10. Additionally, in order to allow the users 30 to verify the obtained event-ordering receipts and verify that the published information is related to the event-ordering receipts in an orderly manner, the users 30 are required to gobble down great volume of data from the event-ordering certification apparatus 10.
Methods for solving part of the above-mentioned problems partially are also proposed. For example, in nonpatent literatures No. 3 (A. Buldas, P. Land, H Lipmaa and J. Villemson: Time-stamping with binary linking schemes, in Processings of Advances on Cryptology (CRYPTO'98), ed. H. Krawczyk, pp. 486-501, Springer-Verlag, 1998) and No. 4 (A. Buldas, H Lipmaa and B. Schoenmakers, Optimally efficient accountable time-stamping, in Proceedings of Public Key Crytography 2000 (PKC2000), eds. Y Zheng and H. Imai, pp. 293-305, Springer-Verlag, January 2000), there is proposed a method of adopting a tree structure in place of the linear lists used in the nonpatent literatures Nos. 1 and 2, in order to calculate publication data collecting up event-ordering requests processed by an event-ordering certification apparatus for a certain period, thereby remarkably reducing the amount of data required for the user 30 to verify an event-ordering receipt, from the amount of data proportional to the number of event-ordering requests accepted for the certain period to the amount of data proportional to a logarithm (base 2) of the former amount.